package algorithm.dijkstra;

import java.util.Arrays;

public class DijkstraAlgorithm {

  public static void main(String[] args) {
    char[]vertex = new char[]{'A','B','C','D','E','F','G'};
    final int N = 65535;//表示不可连接
    int[][]matrix = new int[][]{
            {N,5,7,N,N,N,2},
            {5,N,N,9,N,N,3},
            {7,N,N,N,8,N,N},
            {N,9,N,N,N,4,N},
            {N,N,8,N,N,5,4},
            {N,N,N,4,5,N,6},
            {2,3,N,N,4,6,N}

    };
//创建图
    Graph graph = new Graph(vertex, matrix);
    graph.showGraph(matrix);

    graph.djs(6);
//    显示结果
    graph.showDijkstra();

  }
}

class Graph{
  private char[]vertex;//存放顶点
  private int[][]matrix;//存放边
  private VisitedVertex vv;//存放已访问的顶点

  public Graph(char[] vertex, int[][] matrix) {
    this.vertex = vertex;
    this.matrix = matrix;
  }

//  显示图
  public void showGraph(int[][]matrix){
    for (int[] link : matrix) {
      System.out.println(Arrays.toString(link));
    }
  }
  public void djs(int index){
    vv = new VisitedVertex(vertex.length, index);
    update(index);
    for (int i = 1; i < vertex.length; i++) {
      index = vv.updateArr();//选择并返回新的访问顶点
      update(index); //更新index顶点到周围顶点的距离和前驱顶点
    }
  }
  //更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点,
  public void update(int index){
    int len = 0;
    for (int j = 0; j < matrix[index].length; j++) {
      //len含义是:出发顶点到index顶点的距离＋从index原点到j顶点的距离的和
      len = vv.getDis(index) + matrix[index][j];
      //如果j顶点没有被访问过，并且len小于出发顶点到j顶点的距离，就需要更新
      if (!vv.in(j) && len < vv.getDis(j)){
        vv.updatePre(j,index);//更新j顶点的前驱为index顶点
        vv.updateDis(j,len);//更新出发顶点到j顶点的距离
      }
    }
  }

//  显示结果的方法
  public void showDijkstra(){
    vv.show();
  }
}
class VisitedVertex{
  private int[]already_arr;//记录各个顶点是否访问过，1表示访问过,0未访问，会动动态更新
  private int[]pre_visited;//每个下标对应的值为前一个顶点下标，会动态更新
  private int[]dis;//记录出发顶点到其他所有原点的距离,比如G为出发顶点,就会记录G到其它顶点的距离，会动态更新,求得的最短距离就会存放到dis

  public VisitedVertex(int length,int index){
    this.already_arr = new int[length];
    this.pre_visited = new int[length];
    this.dis = new int[length];
//    初始化dis
    Arrays.fill(dis,65535);
//    设置出发顶点为1
    already_arr[index] = 1;
    dis[index] = 0;
  }

//  判断顶点是否被访问过
  public boolean in(int index){
    return already_arr[index] == 1;
  }
//  更新出发顶点到index的距离
  public void updateDis(int index,int len){
    dis[index] = len;
  }
//  更新顶点的前驱顶点为index这个顶点
  public void updatePre(int pre,int index){
    pre_visited[pre] = index;
  }
//  返回出发顶点到index顶点的距离
  public int getDis(int index){
    return dis[index];
  }
//  继续选择并返回新的访问顶点，比如这里的G完后，就是A点作为新的访问顶点(注意不是出发顶点)
  public int  updateArr(){
    int min = 65525,index = 0;
    for (int i = 0; i < already_arr.length; i++) {
      if (already_arr[i] == 0 && dis[i] < min){
        min = dis[i];
        index = i;
      }
    }
    already_arr[index] = 1;
    return index;
  }
//  显示三个数组
  public void show(){
    System.out.println("=========================");
    for (int i = 0; i < already_arr.length; i++) {
      System.out.print(already_arr[i] + " ");
    }
    System.out.println();
    for (int i = 0; i < pre_visited.length; i++) {
      System.out.print(pre_visited[i] + " ");
    }
    System.out.println();
    for (int i = 0; i < dis.length; i++) {
      System.out.print(dis[i] + " ");
    }
    System.out.println();

    char[]vertex = new char[]{'A','B','C','D','E','F','G'};
    int count = 0;
    for (int ele : dis) {
      if (ele != 65535){
        System.out.print(vertex[count] + "(" + ele + ")");
      }else {
        System.out.println("N");
      }
      count++;
    }
  }

}
